#include <cstdio>
#include <cstring>
#define INF 1000000000

int min( int a, int b ) { return ( a < b )? a: b; }
int max( int a, int b ) { return ( a > b )? a: b; }
struct Node
{
    int l, r, f;
};

int n;
char s1[ 1000001 ], s2[ 1000001 ];
Node a[ 4000001 ];

void init( )
{
    int i, pos = 1;
    n = max( strlen( s1 ), strlen( s2 ) );
    while ( pos < n ) pos <<= 1;
    for ( i = pos; i < pos + n; i++ )
    {
        a[ i ].l = a[ i ].r = i - pos + 1;
        if ( s1[ i - pos ] != s2[ i - pos ] )
            a[ i ].f = i - pos + 1;
        else
            a[ i ].f = INF;
    }
    for ( i = pos + n; i < pos * 2; i++ )
    {
        a[ i ].l = a[ i ].r = i - pos + 1;
        a[ i ].f = INF;
    }
    for ( i = pos - 1; i >= 1; i-- )
    {
        a[ i ].l = a[ i * 2 ].l;
        a[ i ].r = a[ i * 2 + 1 ].r;
        a[ i ].f = min( a[ i * 2 ].f, a[ i * 2 + 1 ].f );
    }
}

void update( int p, int l, int r )
{
    if ( l > a[ p ].r || r < a[ p ].l ) return ;
    if ( l < a[ p ].l ) l = a[ p ].l;
    if ( r > a[ p ].r ) r = a[ p ].r;
    if ( l == a[ p ].l && r == a[ p ].r )
    {
        if ( s1[ l - 1 ] == s2[ l - 1 ] )
            a[ p ].f = INF;
        else
            a[ p ].f = l;
    }
    else
    {
        update( p * 2, l, r );
        update( p * 2 + 1, l, r );
        a[ p ].f = min( a[ p * 2 ].f, a[ p * 2 + 1 ].f );
    }
}

int query( int p, int l, int r )
{
    if ( l > a[ p ].r || r < a[ p ].l ) return INF;
    if ( l < a[ p ].l ) l = a[ p ].l;
    if ( r > a[ p ].r ) r = a[ p ].r;
    if ( l == a[ p ].l && r == a[ p ].r ) return a[ p ].f;
    return min( query( p * 2, l, r ), query( p * 2 + 1, l, r ) );
}

int main( )
{
    int t, cas = 1, m, cmd, i, t1, ans;
    char t2[ 2 ];
    scanf("%d", &t);
    while ( t-- )
    {
        memset( s1, 0, sizeof( s1 ) );
        memset( s2, 0, sizeof( s2 ) );
        scanf("%s%s%d", s1, s2, &m);
        printf("Case %d:\n", cas++);
        init( );
        while ( m-- )
        {
            scanf("%d", &cmd);
            if ( cmd == 1 )
            {
                scanf("%d%d%s", &t1, &i, t2);
                if ( t1 == 1 )
                    s1[ i ] = t2[ 0 ];
                else
                    s2[ i ] = t2[ 0 ];
                update( 1, i + 1, i + 1 );
            }
            else
            {
                scanf("%d", &i);
                printf("%d\n", min( n + 1, query( 1, i + 1, n ) ) - i - 1);
            }
        }
    }
    return 0;
}
